from collections import deque  # 添加导入

def swap(s, x, nx):
    l = list(s)
    l[x], l[nx] = l[nx], l[x]
    return ''.join(l)

def bfs(s):
    global end
    q = deque()  # 将列表改为deque
    v = set()  # 记录已访问状态，避免重复
    n = 9  # 环形排列的盘子总数
    q.append((s, 0))
    v.add(s)
    d = [-1, 1, 2, -2]
    while q:
        new, step = q.popleft()  # 改用popleft提高效率
        if new == end:
            return step
        # 定位空盘位置（索引从0开始）
        x = new.index('0')
        for i in range(4):
            # 计算新位置（环形处理）
            nx = (x + d[i]) % n
            new_str = swap(new, x, nx)
            if new_str not in v:
                q.append((new_str, step + 1))
                v.add(new_str)
    return -1  # 添加找不到解的兜底返回

s = "012345678"
end = "087654321"
ans = bfs(s)
print(ans)